#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        int left = 0, right = 0;
        while (right < nums.size())
        {
            int nextleft = right + 1;
            int nextright = 0;
            for (int j = left; j <= right; j++)
            {
                nextright = max(j + nums[j], nextright);
            }
            if (nextright >= nums.size() - 1) return true;
            if (nextleft > nextright) return false;
            left = nextleft;
            right = nextright;
        }
        return true;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int preMin = prices[0];
        int ret = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] < preMin) preMin = prices[i];
            ret = max(ret, prices[i] - preMin);
        }

        return ret;
    }
};
class MedianFinder
{
    priority_queue<int> st1;
    priority_queue<int, vector<int>, greater<int>> st2;
public:
    MedianFinder()
    {}

    void addNum(int num)
    {
        int m = st1.size();
        int n = st2.size();
        if (m == n)
        {
            if (m == 0 || num <= st1.top()) st1.push(num);
            else
            {
                st2.push(num);
                st1.push(st2.top());
                st2.pop();
            }
        }
        else if (m == n + 1)
        {
            if (num > st1.top()) st2.push(num);
            else
            {
                st1.push(num);
                st2.push(st1.top());
                st1.pop();
            }
        }
    }

    double findMedian()
    {
        int m = st1.size(), n = st2.size();
        if (m == n + 1) return st1.top();
        else return (st1.top() + st2.top()) / 2.0;
    }
};

class Solution {
public:
    using PII = pair<int, int>;
    struct cmp
    {
        bool operator()(PII p1, PII p2)
        {
            return p1.second > p2.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (auto e : nums) hash[e]++;

        priority_queue<PII, vector<PII>, cmp> pq;
        for (auto e : hash)
        {
            if (pq.size() < k) pq.push({ e.first, e.second });
            else
            {
                if (e.second > pq.top().second)
                {
                    pq.pop();
                    pq.push({ e.first, e.second });
                }
            }
        }

        vector<int> ret;
        while (pq.size())
        {
            auto top = pq.top();
            pq.pop();
            ret.push_back(top.first);
        }

        return ret;
    }
};

class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(nullptr));
        return _findKthLargest(nums, 0, nums.size() - 1, k);
    }
    int GetKey(vector<int>& nums, int begin, int end)
    {
        return nums[rand() % (end - begin + 1) + begin];
    }
    int _findKthLargest(vector<int>& nums, int begin, int end, int k)
    {
        int key = GetKey(nums, begin, end);
        int left = begin - 1, right = end + 1;
        int cur = begin;
        while (cur < right)
        {
            if (nums[cur] < key) swap(nums[++left], nums[cur++]);
            else if (nums[cur] == key) cur++;
            else swap(nums[--right], nums[cur]);
        }
        int a = end - right + 1, b = right - left - 1;
        if (a >= k) return _findKthLargest(nums, right, end, k);
        else if (a + b >= k) return key;
        else return _findKthLargest(nums, begin, left, k - a - b);
    }
};
class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);

        int n = heights.size();
        int ret = 0;

        st.push(0);
        for (int i = 1; i < n; )
        {
            if (heights[i] >= heights[st.top()])
            {
                st.push(i);
                i++;
            }
            else
            {
                while (heights[i] < heights[st.top()])
                {
                    int cur = st.top();
                    st.pop();
                    ret = max(ret, heights[cur] * (i - st.top() - 1));
                }
            }
        }
        return ret;
    }
};
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t)
    {
        stack<int> st;
        int n = t.size();
        vector<int> ans(n);

        for (int i = 0; i < n; )
        {
            if (st.empty() || t[i] <= t[st.top()])
            {
                st.push(i);
                i++;
            }
            else
            {
                while (st.size() && t[i] > t[st.top()])
                {
                    ans[st.top()] = i - st.top();
                    st.pop();
                }
            }
        }

        return ans;
    }
};
